题目分析

第一次做这个题目的时候，犯了一个错误，没有注意到不能打乱其他字符的相对位置这个要求，也正是因为这个要求让这个题目的难度上升了一个档次，小伙伴们想一想如何解答？

栈

我们分析下面几种场景

1. 如果当前字符已经出现在res中，那么直接跳过。如res = “bc”，此时遍历到b，b已经存在res中，遍历下一个字符。
2. 如果res为空或者当前字符大于res中的最后一个字符或者res最后一个字符在后面不会出现，那么直接将该字符放在末尾。如res = “bc”，此时遍历到d，那么res = “bcd”一定是最优解。
3. 如果当前字符小于res中的最后一个字符，并且res最后一个字符在后面还会出现，如样例1中s = “bcabc”，res = “bc”，此时遍历到a，c < a，而且c在a后面还出现过，那么将c弹出，到a后面的c出现的时候在插入，这样的字典序会更小。

分析了这三个场景，我们用样例2来模拟这个过程。

因为s由小写英文字母组成，建立一个长度为26的数组，其中保存每一个字符最后出现的位置，这样就可以判断该某个字符在后面是否还会出现。如c最后出现的位置是5，此时遍历到第3个元素a，那么就可以将c弹出，因为在3后面还会有c出现。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
    string removeDuplicateLetters(string s) {
        vector<int> alpha(26);
        vector<bool> visited(26, false);
        string res;
        for (int i = 0; i < s.size(); i++) { alpha[s[i] - 'a'] = i; }
        for (int i = 0; i < s.size(); i++) {
            if (!visited[s[i] - 'a']) {
                while (res.size() && res.back() > s[i] && alpha[res.back() - 'a'] > i) {
                    visited[res.back() - 'a'] = false;
                    res.pop_back();
                }
                res.push_back(s[i]);
                visited[res.back() - 'a'] = true;
            }
        }
        return res;
    }
};

刷题总结

这是一个栈的变形问题，稍微困难一些，不容易想到栈的方法去解答，这时候我们可以模拟输出的过程，可能会引导我们想出栈的思路。